package com.leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zfl
 * @Classname TwoSum
 * @Description 和为s的两个数
 * @Date 2020/11/26 14:36
 */
public class TwoSum {

    /**
     * @param nums
     * @param target
     * @return int[]
     * 利用数组是递增的这一特性
     * 执行用时：75 ms, 在所有 Java 提交中击败了5.01%的用户
     * 内存消耗：59.3 MB, 在所有 Java 提交中击败了5.05%的用户
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] twoNum = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i  < nums.length; i++) {
            map.put(nums[i],i);
        }

        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                twoNum[0] = nums[i];
                twoNum[1] = target - nums[i];
                return twoNum;
            }
        }
        return new int[2];
    }

    /**
     * @param nums
     * @param target
     * @return
     * 执行用时：2 ms, 在所有 Java 提交中击败了97.74%的用户
     * 内存消耗：55.5 MB, 在所有 Java 提交中击败了59.41%的用户
     */
    public static int[] twoSum2(int[] nums,int target) {
        int i = 0, j = nums.length - 1,sum = 0;
        while (i < j) {
            sum = nums[i] + nums[j];
            if(sum < target) {
                i++;
            }else if(sum > target) {
                j--;
            }else {
                return new int[] {nums[i],nums[j]};
            }
        }
        return new int[2];
    }
}
